package com.biancheng.biancheng.biancheng3;

public class 背包问题2 {

    // 问题描述：有n个物品，他们的质量和价值分别为w[i]和v[i]，现在有一个容量为C的背包，要求选择性的放入物品使该背包的价值最大。

    public static void main(String[] args) {
        背包问题2 ff = new 背包问题2();
        int  result  = ff.backpack(new int[]{1,4,3},new int[]{1500,3000,2000},4);
        System.out.println(result);
    }

    public int backpack(int[] w, int[] v, int size) {
        if (w.length != v.length) return -1;
        int n = w.length;
        if (n == 0) return 0;
        int[][] memo1 = new int[n][size + 1];

        for (int i = 0; i <= size; i++) {
            memo1[0][i] = (i >= w[0] ? v[0] : 0);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= size; j++) {
                memo1[i][j] = memo1[i - 1][j];
                if (j >= w[i]) {
                    memo1[i][j] = Math.max(memo1[i][j], v[i] + memo1[i - 1][j - w[i]]);
                }
            }
        }
        return memo1[n - 1][size];
    }




}
